/*------------------------------------------------------------------------
*
* geqo_ox2.c
*
*	 顺序交叉 [OX] 例程；
*	 根据 Syswerda 的 OX2 运算符
*	 (遗传算法手册，编辑 L Davis)
*
* src/backend/optimizer/geqo/geqo_ox2.c
*
*-------------------------------------------------------------------------
*/

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* ox 算法是从 Genitor 采用的： */
/*************************************************************/
/*															 */
/*	Copyright (c) 1990										 */
/*	Darrell L. Whitley										 */
/*	计算机科学系									         */
/*	科罗拉多州立大学									     */
/*															 */
/*	特此允许复制本程序的全部或部分以进行自由分发。作者的姓名  */
/*	及本版权声明必须包含在任何复制中。 */
/* geqo_copy
 *
 *	 将一个基因复制到另一个
 *
 */
/*															 */
/*************************************************************/

#include "postgres.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

#if defined(OX2)

/* ox2
 *
 *	 位置交叉
 */
void ox2(PlannerInfo *fc_root, Gene *fc_tour1, Gene *fc_tour2, Gene *fc_offspring, int fc_num_gene, City * fc_city_table)
{
	int			fc_k,
				fc_j,
				fc_count,
				fc_pos,
				fc_select,
				fc_num_positions;

	/* 初始化城市表 */
	for (fc_k = 1; fc_k <= fc_num_gene; fc_k++)
	{
		fc_city_table[fc_k].used = 0;
		fc_city_table[fc_k - 1].select_list = -1;
	}

	/* 确定要从 tour1 继承的位置数量 */
	fc_num_positions = geqo_randint(fc_root, 2 * fc_num_gene / 3, fc_num_gene / 3);

	/* 制作已选择城市的列表 */
	for (fc_k = 0; fc_k < fc_num_positions; fc_k++)
	{
		fc_pos = geqo_randint(fc_root, fc_num_gene - 1, 0);
		fc_city_table[fc_pos].select_list = (int) fc_tour1[fc_pos];
		fc_city_table[(int) fc_tour1[fc_pos]].used = 1;	/* 标记已使用 */
	}


	fc_count = 0;
	fc_k = 0;

	/* 合并选择列表到相邻位置 */
	while (fc_count < fc_num_positions)
	{
		if (fc_city_table[fc_k].select_list == -1)
		{
			fc_j = fc_k + 1;
			while ((fc_city_table[fc_j].select_list == -1) && (fc_j < fc_num_gene))
				fc_j++;

			fc_city_table[fc_k].select_list = fc_city_table[fc_j].select_list;
			fc_city_table[fc_j].select_list = -1;
			fc_count++;
		}
		else
			fc_count++;
		fc_k++;
	}

	fc_select = 0;

	for (fc_k = 0; fc_k < fc_num_gene; fc_k++)
	{
		if (fc_city_table[(int) fc_tour2[fc_k]].used)
		{
			fc_offspring[fc_k] = (Gene) fc_city_table[fc_select].select_list;
			fc_select++;			/* 选择列表中的下一个城市 */
		}
		else
			/* 城市尚未使用，因此从 tour2 继承 */
			fc_offspring[fc_k] = fc_tour2[fc_k];
	}
}

#endif							/* 定义（OX2） */
